{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Check Balance LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isBalanced"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #检查平衡性"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个节点，其两棵子树的高度差不超过 1。</p><br><strong>示例 1:</strong><pre>给定二叉树 [3,9,20,null,null,15,7]<br>    3<br>   / &#92<br>  9  20<br>    /  &#92<br>   15   7<br>返回 true 。</pre><strong>示例 2:</strong><br><pre>给定二叉树 [1,2,2,3,3,null,null,4,4]<br>      1<br>     / &#92<br>    2   2<br>   / &#92<br>  3   3<br> / &#92<br>4   4<br>返回 false 。</pre>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [check-balance-lcci](https://leetcode.cn/problems/check-balance-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [check-balance-lcci](https://leetcode.cn/problems/check-balance-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def dfs(root):\n",
    "            if root:\n",
    "                lh, lb = dfs(root.left)\n",
    "                rh, rb = dfs(root.right)\n",
    "                return max(lh, rh)+1, lb and rb and abs(lh-rh)<=1\n",
    "            else:\n",
    "                return 0, True\n",
    "        return dfs(root)[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def height(root: TreeNode) -> int:\n",
    "            if not root:\n",
    "                return 0\n",
    "            return max(height(root.left), height(root.right)) + 1\n",
    "\n",
    "        if not root:\n",
    "            return True\n",
    "        return abs(height(root.left) - height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def height(root: TreeNode) -> int:\n",
    "            if not root:\n",
    "                return 0\n",
    "            \n",
    "            leftHeight = height(root.left)\n",
    "            rightHeight = height(root.right)\n",
    "            if leftHeight==-1 or rightHeight==-1 or abs(leftHeight-rightHeight)>1:\n",
    "                return -1\n",
    "            else:\n",
    "                return max(leftHeight,rightHeight) + 1\n",
    "        \n",
    "        return height(root) >= 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 计算以当前节点为根的树深度\n",
    "    def Depth(self, root: TreeNode) -> int:\n",
    "        if root:\n",
    "            return 1 + max(self.Depth(root.left), self.Depth(root.right))\n",
    "        return 0\n",
    "\n",
    "\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        # 空树是AVL\n",
    "        if not root:\n",
    "            return True\n",
    "        # 若左右子树深度超过1，非AVL\n",
    "        if abs(self.Depth(root.left) - self.Depth(root.right)) > 1:\n",
    "            return False\n",
    "        # 递归执行，当出现不满足AVL性质的子树时，执行短路运算立即返回结果\n",
    "        return self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def height(root: TreeNode):\n",
    "            if not root:\n",
    "                return 0\n",
    "            return 1+max(height(root.left),height(root.right))\n",
    "        if not root:\n",
    "            return True\n",
    "        return abs(height(root.left)-height(root.right))<=1 and self.isBalanced(root.left) and self.isBalanced(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        ans = True\n",
    "\n",
    "        def depth(n):\n",
    "            nonlocal ans\n",
    "            if n is None:\n",
    "                return 0\n",
    "            left =  depth(n.left)\n",
    "            right = depth(n.right)\n",
    "\n",
    "            if abs(left - right) > 1:\n",
    "                ans = False\n",
    "\n",
    "            return max(left, right) + 1\n",
    "\n",
    "        depth(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "       res = True\n",
    "       def dfs(root: TreeNode) -> int:\n",
    "          nonlocal res\n",
    "          if root is None or not res:\n",
    "             return 0\n",
    "          left = dfs(root.left) + 1\n",
    "          right = dfs(root.right) + 1\n",
    "          if abs(left - right) > 1:\n",
    "             res = False\n",
    "          return max(left, right)\n",
    "       dfs(root)\n",
    "       return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def treehigh(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            return max(treehigh(node.left), treehigh(node.right)) + 1\n",
    "        if not root:\n",
    "            return True\n",
    "        if abs(treehigh(root.left) - treehigh(root.right)) <= 1:\n",
    "            return self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if root is None:\n",
    "            return True\n",
    "\n",
    "        def depth(n):\n",
    "            if n is None:\n",
    "                return 0\n",
    "            return max(depth(n.left), depth(n.right)) + 1\n",
    "\n",
    "        if abs(depth(root.left) - depth(root.right)) > 1:\n",
    "            return False\n",
    "\n",
    "        return self.isBalanced(root.left) and self.isBalanced(root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def MaxDepth(self, root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        depth1 = self.MaxDepth(root.left)\n",
    "        depth2 = self.MaxDepth(root.right)\n",
    "        if depth1 > depth2:\n",
    "            depth = depth1\n",
    "        else:\n",
    "            depth = depth2\n",
    "        depth += 1\n",
    "        return depth\n",
    "\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if root is None:\n",
    "            return True\n",
    "        depth1 = self.MaxDepth(root.left)\n",
    "        depth2 = self.MaxDepth(root.right)\n",
    "        if abs(depth2 - depth1) > 1:\n",
    "            return False\n",
    "        return self.isBalanced(root.left) and self.isBalanced(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def height(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            else:\n",
    "                return max(height(root.left), height(root.right)) + 1\n",
    "\n",
    "        if not root:\n",
    "            return True\n",
    "        if abs(height(root.left) - height(root.right)) > 1:\n",
    "            return False\n",
    "        return self.isBalanced(root.right) and self.isBalanced(root.left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def height(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            else:\n",
    "                return max(height(root.left), height(root.right)) + 1\n",
    "\n",
    "        if not root:\n",
    "            return True\n",
    "        if abs(height(root.left) - height(root.right)) > 1:\n",
    "            return False\n",
    "        return self.isBalanced(root.right) and self.isBalanced(root.left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "\n",
    "        flag = 1\n",
    "        def suforder(node):\n",
    "            nonlocal flag\n",
    "            if not node:\n",
    "                return 0\n",
    "            \n",
    "            left = suforder(node.left)\n",
    "            right = suforder(node.right)\n",
    "            if abs(left - right) > 1:\n",
    "                flag = 0\n",
    "            return max(left, right) + 1\n",
    "        \n",
    "        suforder(root)\n",
    "        return flag == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "\tdef isBalanced(self, root: TreeNode) -> bool:\n",
    "\t\tdef check(root):\n",
    "\t\t\tif not root:\n",
    "\t\t\t\treturn 0\n",
    "\t\t\tleft_check = check(root.left)\n",
    "\t\t\tright_check = check(root.right)\n",
    "\t\t\tif left_check == -1 or right_check == -1 or abs(left_check - right_check) > 1:\n",
    "\t\t\t\treturn -1\n",
    "\t\t\telse:\n",
    "\t\t\t\treturn max(left_check, right_check) + 1\n",
    "\n",
    "\t\treturn check(root) >= 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# class Solution:\n",
    "#     def isBalanced(self, root: TreeNode) -> bool:\n",
    "#         if root == None:\n",
    "#             return True\n",
    "#         ans=self.bp(root)\n",
    "#         return ans>=0\n",
    "    \n",
    "#     def bp(self, root: TreeNode):\n",
    "#         if root.left == None and root.right == None:\n",
    "#             return 1\n",
    "#         ln=0\n",
    "#         rn=0\n",
    "#         if root.left !=None:\n",
    "#             ln=self.bp(root.left)\n",
    "#         if root.right!=None:\n",
    "#             rn=self.bp(root.right)\n",
    "#         if ln ==-1 or rn ==-1:\n",
    "#             return -1\n",
    "#         if abs(ln-rn)>=2:\n",
    "#             return -1\n",
    "#         return max(ln,rn)+1\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def height(root: TreeNode) -> int:\n",
    "            if not root:\n",
    "                return 0\n",
    "            return max(height(root.left), height(root.right)) + 1\n",
    "\n",
    "        if not root:\n",
    "            return True\n",
    "        return abs(height(root.left) - height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        \n",
    "        def get_depth(root):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            left = get_depth(root.left)\n",
    "            right = get_depth(root.right)\n",
    "            if left == -1 or right == -1 or abs(left - right) > 1:\n",
    "                return -1\n",
    "            else:\n",
    "                return 1 + max(left, right)\n",
    "        \n",
    "        return get_depth(root) >= 0\n",
    "\n",
    "        if root is None:\n",
    "            return True\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def checkHeight(root):\n",
    "            if not root: return -1\n",
    "\n",
    "            leftHeight = checkHeight(root.left)\n",
    "            if leftHeight == float('inf'): return float('inf') # 向上传递错误\n",
    "\n",
    "            rightHeight = checkHeight(root.right)\n",
    "            if rightHeight == float('inf'): return float('inf') # 向上传递错误\n",
    "\n",
    "            heightDiff = leftHeight - rightHeight\n",
    "            if abs(heightDiff) > 1:\n",
    "                return float('inf') # 发现错误，把它传回来\n",
    "            else:\n",
    "                return max(leftHeight, rightHeight) + 1\n",
    "\n",
    "        return checkHeight(root) != float('inf')\n",
    "\n",
    "# 作者：腐烂的橘子\n",
    "# 链接：https://leetcode.cn/problems/check-balance-lcci/solutions/185819/di-gui-fang-wen-de-gao-du-python3-by-z1m/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def hight(root):\n",
    "            if not root: return 0\n",
    "            else:\n",
    "                return max(hight(root.left), hight(root.right)) + 1\n",
    "        if not root:\n",
    "            return True\n",
    "        if abs(hight(root.left) - hight(root.right)) > 1:\n",
    "            return False\n",
    "        return self.isBalanced(root.right) and self.isBalanced(root.left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if root is None:\n",
    "            return True\n",
    "        left_height = self.height(root.left)\n",
    "        right_height = self.height(root.right)\n",
    "\n",
    "        if abs(left_height - right_height) > 1:\n",
    "            return False\n",
    "        \n",
    "        return self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "        \n",
    "    \n",
    "    def height(self, root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        left_height = self.height(root.left) + 1\n",
    "        right_height = self.height(root.right) + 1\n",
    "\n",
    "        return max(left_height, right_height)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def Depth(self,root: TreeNode) ->int:\n",
    "        if root:\n",
    "            return 1 + max(self.Depth(root.left),self.Depth(root.right))\n",
    "        return 0\n",
    "\n",
    "        \n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root: return True\n",
    "        if abs(self.Depth(root.left) - self.Depth(root.right)) > 1: return False\n",
    "        return self.isBalanced(root.left) and self.isBalanced(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "\tdef isBalanced(self, root: TreeNode) -> bool:\n",
    "\t\tdef get_height(root):\n",
    "\t\t\tif not root:\n",
    "\t\t\t\treturn 0\n",
    "\t\t\treturn max(get_height(root.left), get_height(root.right)) + 1\n",
    "\n",
    "\t\tif not root:\n",
    "\t\t\treturn True\n",
    "\t\treturn abs(get_height(root.left) - get_height(root.right)) <= 1 and self.isBalanced(\n",
    "\t\t\troot.left) and self.isBalanced(root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def height(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            return max(height(root.left),height(root.right))+1\n",
    "        if not root:\n",
    "            return True\n",
    "        return abs(height(root.left)-height(root.right))<=1 and self.isBalanced(root.left) and self.isBalanced(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# class Solution:\n",
    "#     def isBalanced(self, root: TreeNode) -> bool:\n",
    "#         if root == None:\n",
    "#             return True\n",
    "#         ans=self.bp(root)\n",
    "#         return ans>=0\n",
    "    \n",
    "#     def bp(self, root: TreeNode):\n",
    "#         if root.left == None and root.right == None:\n",
    "#             return 1\n",
    "#         ln=0\n",
    "#         rn=0\n",
    "#         if root.left !=None:\n",
    "#             ln=self.bp(root.left)\n",
    "#         if root.right!=None:\n",
    "#             rn=self.bp(root.right)\n",
    "#         if ln ==-1 or rn ==-1:\n",
    "#             return -1\n",
    "#         if abs(ln-rn)>=2:\n",
    "#             return -1\n",
    "#         return max(ln,rn)+1\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def height(root: TreeNode) -> int:\n",
    "            if not root:\n",
    "                return 0\n",
    "            return max(height(root.left), height(root.right)) + 1\n",
    "\n",
    "        if not root:\n",
    "            return True\n",
    "        return abs(height(root.left) - height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 计算以当前节点为根的树深度\n",
    "    def Depth(self, root: TreeNode) -> int:\n",
    "        # 子树的最大深度\n",
    "        if root:\n",
    "            return 1 + max(self.Depth(root.left), self.Depth(root.right))\n",
    "        return 0\n",
    "\n",
    "\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        # 空树是AVL\n",
    "        if not root:\n",
    "            return True\n",
    "        # 若左右子树深度超过1，非AVL\n",
    "        if abs(self.Depth(root.left) - self.Depth(root.right)) > 1:\n",
    "            return False\n",
    "        # 递归执行，当出现不满足AVL性质的子树时，执行短路运算立即返回结果\n",
    "        return self.isBalanced(root.left) and self.isBalanced(root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def compute(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            left_height = compute(root.left)\n",
    "            right_height = compute(root.right)\n",
    "            if left_height == -1 or right_height == -1 or abs(left_height - right_height) > 1:\n",
    "                return -1\n",
    "            return max(left_height, right_height) + 1\n",
    "        return compute(root) >= 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def calcDegree(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            return max(calcDegree(root.left), calcDegree(root.right)) + 1\n",
    "        if not root:\n",
    "            return True\n",
    "        return abs(calcDegree(root.left) - calcDegree(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def walk(self, root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        else:\n",
    "            left = self.walk(root.left)\n",
    "            right = self.walk(root.right)\n",
    "            if abs(left-right)>1:\n",
    "                self.ret = False\n",
    "            return max(left, right) + 1\n",
    "\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        self.ret = True\n",
    "        self.walk(root)\n",
    "        return self.ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def Depth(self, root: TreeNode) -> int:\n",
    "        if root:\n",
    "            return 1 + max(self.Depth(root.left), self.Depth(root.right))\n",
    "        return 0\n",
    "\n",
    "\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        if abs(self.Depth(root.left) - self.Depth(root.right)) > 1:\n",
    "            return False\n",
    "        return self.isBalanced(root.left) and self.isBalanced(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        res = True\n",
    "        def geth(root):\n",
    "            nonlocal res\n",
    "            if not res: return\n",
    "            if not root: return 0\n",
    "            hl = geth(root.left)\n",
    "            if not res: return\n",
    "            hr = geth(root.right)\n",
    "            if not res: return\n",
    "            if abs(hl - hr) > 1:\n",
    "                res = False\n",
    "                return\n",
    "            return max(hl, hr) + 1\n",
    "        \n",
    "        geth(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "\n",
    "        def isBal(left,right):\n",
    "            dleft,dright=0,0\n",
    "            if left:\n",
    "                dleft= isBal(left.left,left.right)\n",
    "            if right:\n",
    "                dright= isBal(right.left,right.right)\n",
    "            \n",
    "            if  dleft!=-1 and dright!=-1 and  abs(dleft-dright)<=1:\n",
    "                return max(dleft,dright)+1\n",
    "            else:\n",
    "                return -1\n",
    "\n",
    "        if not root:\n",
    "            return True\n",
    "\n",
    "        return  isBal(root.left,root.right) !=-1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if root == None:\n",
    "            return True\n",
    "        ans=self.bp(root)\n",
    "        return ans>=0\n",
    "    \n",
    "    def bp(self, root: TreeNode):\n",
    "        if root.left == None and root.right == None:\n",
    "            return 1\n",
    "        ln=0\n",
    "        rn=0\n",
    "        if root.left !=None:\n",
    "            ln=self.bp(root.left)\n",
    "        if root.right!=None:\n",
    "            rn=self.bp(root.right)\n",
    "        if ln ==-1 or rn ==-1:\n",
    "            return -1\n",
    "        if abs(ln-rn)>=2:\n",
    "            return -1\n",
    "        return max(ln,rn)+1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def height(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            else:\n",
    "                return max(height(root.left), height(root.right)) + 1\n",
    "\n",
    "        if not root:\n",
    "            return True\n",
    "        if abs(height(root.left) - height(root.right)) > 1:\n",
    "            return False\n",
    "        return self.isBalanced(root.left) and self.isBalanced(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = True\n",
    "\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        self.traverse(root)\n",
    "        return self.res\n",
    "\n",
    "    def traverse(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        left = self.traverse(root.left)\n",
    "        right = self.traverse(root.right)\n",
    "        if abs(left - right) > 1:\n",
    "            self.res = False\n",
    "        return max(left, right) + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def Depth(self, root: TreeNode) -> int:\n",
    "        if root:\n",
    "            return 1 + max(self.Depth(root.left), self.Depth(root.right))\n",
    "        return 0\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        # 若左右子树深度超过1，非AVL\n",
    "        if abs(self.Depth(root.left) - self.Depth(root.right)) > 1:\n",
    "            return False\n",
    "        # 递归执行，当出现不满足AVL性质的子树时，执行短路运算立即返回结果\n",
    "        return self.isBalanced(root.left) and self.isBalanced(root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "\n",
    "        def is_bitree(node):\n",
    "            if node is None:\n",
    "                return (True, 1)\n",
    "            is_r, l_r = is_bitree(node.right)\n",
    "            is_l, l_l = is_bitree(node.left)\n",
    "            if (is_r is False) or (is_l is False) or (abs(l_r - l_l) > 1):\n",
    "                return False, max(l_r, l_l) + 1\n",
    "            else:\n",
    "                return True, max(l_r, l_l) + 1\n",
    "        is_tree, high = is_bitree(root)\n",
    "        return is_tree\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "\n",
    "        def dfs(root: TreeNode) -> int:\n",
    "            if not root:\n",
    "                return 0\n",
    "            \n",
    "            ld = dfs(root.left)\n",
    "            rd = dfs(root.right)\n",
    "\n",
    "            if abs(ld - rd) > 1 or ld < 0 or rd < 0:\n",
    "                return -1\n",
    "            \n",
    "            return max(ld, rd) + 1\n",
    "        \n",
    "        return dfs(root) >= 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def compute(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            return max(compute(root.left) + 1, compute(root.right) + 1)\n",
    "        if not root:\n",
    "            return True\n",
    "        if abs(compute(root.left) - compute(root.right)) > 1:\n",
    "            return False\n",
    "        return self.isBalanced(root.left) and self.isBalanced(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root:return True\n",
    "        def func(root):\n",
    "            if not root:\n",
    "                return 0, True\n",
    "            left = func(root.left)\n",
    "            right = func(root.right)\n",
    "            return max(left[0],right[0])+1,left[1] and right[1] and -1<=left[0]-right[0]<=1\n",
    "        left = func(root.left)\n",
    "        right = func(root.right)\n",
    "        return left[1] and right[1] and -1<=left[0]-right[0]<=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def height(node):\n",
    "            if node is None:\n",
    "                return 0\n",
    "            return max(height(node.left), height(node.right)) + 1\n",
    "        if not root:\n",
    "            return True\n",
    "        return abs(height(root.left) - height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 计算以当前节点为根的树深度\n",
    "    def Depth(self, root: TreeNode) -> int:\n",
    "        if root:\n",
    "            return 1 + max(self.Depth(root.left), self.Depth(root.right))\n",
    "        return 0\n",
    "\n",
    "\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        # 空树是AVL\n",
    "        if not root:\n",
    "            return True\n",
    "        # 若左右子树深度超过1，非AVL\n",
    "        if abs(self.Depth(root.left) - self.Depth(root.right)) > 1:\n",
    "            return False\n",
    "        # 递归执行，当出现不满足AVL性质的子树时，执行短路运算立即返回结果\n",
    "        return self.isBalanced(root.left) and self.isBalanced(root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def depth(self,root:TreeNode) -> int :\n",
    "        if root :\n",
    "            return 1+max(self.depth(root.left),self.depth(root.right))\n",
    "        return 0 \n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        if abs(self.depth(root.left)-self.depth(root.right)) > 1:\n",
    "            return False\n",
    "        return self.isBalanced(root.left) and self.isBalanced(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def h(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            return max(h(node.left), h(node.right)) + 1\n",
    "        if not root:\n",
    "            return True\n",
    "        return abs(h(root.left) - h(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# ### my:dfs\n",
    "# class Solution:\n",
    "#     def isBalanced(self, root: TreeNode) -> bool:\n",
    "#         def dfs(node):\n",
    "#             if not node:\n",
    "#                 return 0,True\n",
    "#             lh,ls=dfs(node.left)\n",
    "#             rh,rs=dfs(node.right)\n",
    "#             return max(lh,rh)+1,ls==True and rs==True and abs(lh-rh)<=1\n",
    "\n",
    "#         rooth,roots=dfs(root)\n",
    "#         return roots \n",
    "\n",
    "# ### 官1：自顶向下（双重递归）\n",
    "# class Solution:\n",
    "#     def isBalanced(self,root): ### 判断平衡性的DFS\n",
    "#         def height(node): ###计算子树高度的DFS\n",
    "#             if not node:return 0\n",
    "#             return max(height(node.left),height(node.right))+1\n",
    "\n",
    "#         if not root:\n",
    "#             return True\n",
    "#         ###左右子树高度<=1 & 左子树是平衡树 & 右子树是平衡树\n",
    "#         return abs(height(root.left)-height(root.right))<=1 and self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "\n",
    "### 官2：自底向上（单递归）\n",
    "class Solution:\n",
    "    def isBalanced(self,root):\n",
    "        def height(node):###计算子树高度，不平衡的子树高度直接返回-1\n",
    "            if not node:\n",
    "                return 0\n",
    "            lh=height(node.left)\n",
    "            rh=height(node.right)\n",
    "            # if abs(lh-rh)>1:\n",
    "            ### 当前树不平衡，或左子树不平衡，或右子树不平衡时，“归”为-1\n",
    "            if abs(lh-rh)>1 or lh==-1 or rh==-1:\n",
    "                return -1\n",
    "            else:\n",
    "                return max(lh,rh)+1\n",
    "        return height(root)>=0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def height(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            \n",
    "            L, R = height(root.left), height(root.right)\n",
    "            if L >= 0 and R >= 0 and abs(L - R) <= 1:\n",
    "                return max(L, R) + 1\n",
    "            else:\n",
    "                return -1\n",
    "        \n",
    "        if height(root) == -1:  return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def height(root: TreeNode) -> int:\n",
    "            if not root:\n",
    "                return 0\n",
    "            leftHeight = height(root.left)\n",
    "            rightHeight = height(root.right)\n",
    "            if leftHeight == -1 or rightHeight == -1 or abs(leftHeight - rightHeight) > 1:\n",
    "                return -1\n",
    "            else:\n",
    "                return max(leftHeight, rightHeight) + 1\n",
    "\n",
    "        return height(root) >= 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def height(root: TreeNode):\n",
    "            if not root: return 0\n",
    "            return 1 + max(height(root.left), height(root.right))\n",
    "        if not root: return True\n",
    "        nodes = [root]\n",
    "        while nodes:\n",
    "            childNode = []\n",
    "            for node in nodes:\n",
    "                print('node.val=', node.val)\n",
    "\n",
    "                if abs(height(node.left) - height(node.right)) > 1:\n",
    "                    print('pass')\n",
    "                    return False\n",
    "                if node.left:\n",
    "                    childNode.append(node.left)\n",
    "                if node.right:\n",
    "                    childNode.append(node.right)\n",
    "            nodes = childNode\n",
    "        return True\n",
    "\n",
    "\n",
    "            # return abs(self.isBalanced(root.left) - self.isBalanced(root.right)) <=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def findheight(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            leftheight = findheight(root.left)\n",
    "\n",
    "            rightheight = findheight(root.right)\n",
    "            if abs(leftheight - rightheight) > 1:\n",
    "                return -1\n",
    "            elif leftheight == -1 or rightheight == -1:\n",
    "                return -1\n",
    "            else:\n",
    "                height = max(leftheight, rightheight) + 1\n",
    "                return height\n",
    "        if findheight(root) == -1:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def height(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            else:\n",
    "                return max(height(root.left), height(root.right)) + 1\n",
    "\n",
    "        if not root:\n",
    "            return True\n",
    "        if abs(height(root.left) - height(root.right)) > 1:\n",
    "            return False\n",
    "        return self.isBalanced(root.right) and self.isBalanced(root.left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def height(root: TreeNode) -> int:\n",
    "            if not root:\n",
    "                return 0\n",
    "            return max(height(root.left), height(root.right)) + 1\n",
    "\n",
    "        if not root:\n",
    "            return True\n",
    "        return abs(height(root.left) - height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root:return True\n",
    "        def func(root):\n",
    "            if not root:\n",
    "                return 0, True\n",
    "            left = func(root.left)\n",
    "            right = func(root.right)\n",
    "            return max(left[0],right[0])+1,left[1] and right[1] and -1<=left[0]-right[0]<=1\n",
    "        left = func(root.left)\n",
    "        right = func(root.right)\n",
    "        return left[1] and right[1] and -1<=left[0]-right[0]<=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        self.ans = True\n",
    "        def dfs(root):\n",
    "            if not root: return 0\n",
    "            l = dfs(root.left)\n",
    "            r = dfs(root.right)\n",
    "            if abs(l - r) > 1:\n",
    "                self.ans = False\n",
    "            # print(root.val, l, r, abs(l - r))\n",
    "            return max(l, r) + 1\n",
    "        dfs(root)\n",
    "        return self.ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# ### my:dfs\n",
    "# class Solution:\n",
    "#     def isBalanced(self, root: TreeNode) -> bool:\n",
    "#         def dfs(node):\n",
    "#             if not node:\n",
    "#                 return 0,True\n",
    "#             lh,ls=dfs(node.left)\n",
    "#             rh,rs=dfs(node.right)\n",
    "#             return max(lh,rh)+1,ls==True and rs==True and abs(lh-rh)<=1\n",
    "\n",
    "#         rooth,roots=dfs(root)\n",
    "#         return roots \n",
    "\n",
    "### 官1：自顶向下（双重递归）\n",
    "class Solution:\n",
    "    def isBalanced(self,root): ### 判断平衡性的DFS\n",
    "        def height(node): ###计算子树高度的DFS\n",
    "            if not node:return 0\n",
    "            return max(height(node.left),height(node.right))+1\n",
    "\n",
    "        if not root:\n",
    "            return True\n",
    "        ###左右子树高度<=1 & 左子树是平衡树 & 右子树是平衡树\n",
    "        return abs(height(root.left)-height(root.right))<=1 and self.isBalanced(root.left) and self.isBalanced(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        ans = True\n",
    "\n",
    "        def dfs(node):\n",
    "            if node is None: return 0\n",
    "            ld, rd = dfs(node.left), dfs(node.right)\n",
    "            if abs(ld - rd) > 1: \n",
    "                nonlocal ans\n",
    "                ans = False\n",
    "                return inf\n",
    "            return max(ld, rd) + 1\n",
    "        \n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def dfs(t):\n",
    "            if not t:\n",
    "                return True, 0\n",
    "            lb, lh = dfs(t.left)\n",
    "            rb, rh = dfs(t.right)\n",
    "            if not lb or not rb or not 0 <= abs(lh - rh) <= 1:\n",
    "                return False, 0\n",
    "            return True, max(lh, rh) + 1\n",
    "        return dfs(root)[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:       \n",
    "        if not root:\n",
    "            return True\n",
    "        def balanced(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            \n",
    "            leftdeep = balanced(root.left)\n",
    "            rightdeep = balanced(root.right)\n",
    "            if leftdeep is False or rightdeep is False:\n",
    "                return False\n",
    "            if max(leftdeep, rightdeep) - min(leftdeep, rightdeep) <= 1:\n",
    "                return max(leftdeep, rightdeep) + 1\n",
    "            else:\n",
    "                return False\n",
    "        deep = balanced(root)\n",
    "        return not deep is False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "            if left == -1 or right == -1 or abs(left-right) > 1:\n",
    "                return -1\n",
    "            else:\n",
    "                return max(left, right) + 1\n",
    "        return dfs(root) >= 0\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        def getHeight(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            left = getHeight(node.left)\n",
    "            right = getHeight(node.right)\n",
    "            return max(left, right)+1\n",
    "        if abs(getHeight(root.left)-getHeight(root.right)) >1:\n",
    "            return False\n",
    "        return self.isBalanced(root.left) and self.isBalanced(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        return self.dfs(root) != -1\n",
    "    def dfs(self, node):\n",
    "        if node is None: return 0\n",
    "        left = self.dfs(node.left)\n",
    "        if left == -1: return -1\n",
    "        right = self.dfs(node.right)\n",
    "        if right == -1: return -1\n",
    "        return -1 if abs(left-right) > 1 else max(left, right)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def dg(root):\n",
    "            if not root:return 0\n",
    "            l = dg(root.left)\n",
    "            if l == -1:return -1\n",
    "            r = dg(root.right)\n",
    "            if r == -1:return -1\n",
    "            return max(l,r)+1 if abs(l - r) <= 1 else -1\n",
    "        return dg(root) != -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def helper(node):\n",
    "            if not node:\n",
    "                return (True, 0)\n",
    "            \n",
    "            leftb, lefth = helper(node.left)\n",
    "            rightb, righth = helper(node.right)\n",
    "            h = max(lefth, righth) + 1\n",
    "            return (leftb and rightb and abs(lefth - righth) <= 1, h)\n",
    "        return helper(root)[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def height(root: TreeNode) -> int:\n",
    "            if not root:\n",
    "                return 0\n",
    "            return max(height(root.left), height(root.right)) + 1\n",
    "\n",
    "        if not root:\n",
    "            return True\n",
    "        return abs(height(root.left) - height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if root is None:\n",
    "            return True\n",
    "        flag = True\n",
    "        def treeHeight(root):\n",
    "            nonlocal  flag\n",
    "            if root is None:\n",
    "                return 0\n",
    "            left = treeHeight(root.left)\n",
    "            right = treeHeight(root.right)\n",
    "            if abs(left - right) > 1:\n",
    "                flag = False\n",
    "            if left > right:\n",
    "                return left + 1\n",
    "            else:return right + 1\n",
    "        treeHeight(root)\n",
    "        return flag\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        hei = self.getHei(root)\n",
    "        return hei != -1\n",
    "\n",
    "    def getHei(self, root: TreeNode) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "\n",
    "        left_hei = self.getHei(root.left)\n",
    "        right_hei = self.getHei(root.right)\n",
    "\n",
    "        if abs(left_hei-right_hei) > 1:\n",
    "            return -1 \n",
    "        if left_hei == -1 or right_hei == -1:\n",
    "            return -1 \n",
    "        \n",
    "        return max(left_hei, right_hei) + 1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        height = self.checkHeight(root)\n",
    "        return height >= 0\n",
    "    \n",
    "    def checkHeight(self, root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        \n",
    "        leftHeight = self.checkHeight(root.left)\n",
    "        if leftHeight < 0:\n",
    "            return -1\n",
    "\n",
    "        rightHeight = self.checkHeight(root.right)\n",
    "        if rightHeight < 0:\n",
    "            return -1\n",
    "\n",
    "        if abs(leftHeight - rightHeight) > 1:\n",
    "            return -1\n",
    "        \n",
    "        return max(leftHeight, rightHeight) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def height(root: TreeNode):\n",
    "            if not root: return 0\n",
    "            return 1 + max(height(root.left), height(root.right))\n",
    "        if not root: return True\n",
    "        if abs(height(root.left) - height(root.right)) > 1:\n",
    "            return False\n",
    "        return self.isBalanced(root.right) and self.isBalanced(root.left)\n",
    "\n",
    "\n",
    "        # nodes = [root]\n",
    "        # while nodes:\n",
    "        #     childNode = []\n",
    "        #     for node in nodes:\n",
    "        #         # print('node.val=', node.val)\n",
    "\n",
    "        #         if abs(height(node.left) - height(node.right)) > 1:\n",
    "        #             # print('pass')\n",
    "        #             return False\n",
    "        #         if node.left:\n",
    "        #             childNode.append(node.left)\n",
    "        #         if node.right:\n",
    "        #             childNode.append(node.right)\n",
    "        #     nodes = childNode\n",
    "        # return True\n",
    "\n",
    "\n",
    "            # return abs(self.isBalanced(root.left) - self.isBalanced(root.right)) <=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "\tdef isBalanced(self, root: TreeNode) -> bool:\n",
    "\t\tdef check(root):\n",
    "\t\t\tif not root:\n",
    "\t\t\t\treturn 0\n",
    "\t\t\tleft_check = check(root.left)\n",
    "\t\t\tright_check = check(root.right)\n",
    "\t\t\tif left_check == -1 or right_check == -1 or abs(left_check - right_check) > 1:\n",
    "\t\t\t\treturn -1\n",
    "\t\t\telse:\n",
    "\t\t\t\treturn max(left_check, right_check) + 1\n",
    "\n",
    "\t\treturn check(root) >= 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def height(node):\n",
    "            if node is None:\n",
    "                return 0\n",
    "            return max(height(node.left), height(node.right)) + 1\n",
    "        if not root:\n",
    "            return True\n",
    "        return abs(height(root.left) - height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "\n",
    "        def Tree(self,root:TreeNode):\n",
    "            if not root:return 0\n",
    "            left=Tree(self,root.left)\n",
    "            if left==-1:return -1\n",
    "            right=Tree(self,root.right)\n",
    "            if right==-1:return -1\n",
    "            return max(left,right)+1 if abs(left-right)<=1 else -1\n",
    "        return False if Tree(self,root)==-1 else True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        height =  self.get_height(root)\n",
    "        return height >= 0\n",
    "\n",
    "    def get_height(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        height_l = self.get_height(root.left)\n",
    "        height_r = self.get_height(root.right)\n",
    "        # 只是用-1代替多出来那个bool返回值，省一个返回值\n",
    "        if height_l == -1 or height_r == -1 or abs(height_l -height_r) > 1:\n",
    "            return -1\n",
    "        else:\n",
    "            height = max(height_l, height_r) + 1\n",
    "            return height"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def height(root: TreeNode):\n",
    "            if not root: return 0\n",
    "            return 1 + max(height(root.left), height(root.right))\n",
    "        if not root: return True\n",
    "        if abs(height(root.left) - height(root.right)) > 1:\n",
    "            return False\n",
    "        return self.isBalanced(root.right) and self.isBalanced(root.left)\n",
    "\n",
    "\n",
    "        # nodes = [root]\n",
    "        # while nodes:\n",
    "        #     childNode = []\n",
    "        #     for node in nodes:\n",
    "        #         # print('node.val=', node.val)\n",
    "\n",
    "        #         if abs(height(node.left) - height(node.right)) > 1:\n",
    "        #             # print('pass')\n",
    "        #             return False\n",
    "        #         if node.left:\n",
    "        #             childNode.append(node.left)\n",
    "        #         if node.right:\n",
    "        #             childNode.append(node.right)\n",
    "        #     nodes = childNode\n",
    "        # return True\n",
    "\n",
    "\n",
    "            # return abs(self.isBalanced(root.left) - self.isBalanced(root.right)) <=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def _isBalanced(self, root: TreeNode) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        l = self._isBalanced(root.left)\n",
    "        if l < 0:\n",
    "            return -1\n",
    "        r = self._isBalanced(root.right)\n",
    "        if r < 0:\n",
    "            return -1\n",
    "        if l > r+1 or r > l+1:\n",
    "            return -1\n",
    "        h = l\n",
    "        if r > h:\n",
    "            h = r\n",
    "        return h+1\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if root is None:\n",
    "            return True\n",
    "        r = self._isBalanced(root)\n",
    "        if r < 0:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def height(root: TreeNode) -> int:\n",
    "            if not root:\n",
    "                return 0\n",
    "            return max(height(root.left), height(root.right)) + 1\n",
    "\n",
    "        if not root:\n",
    "            return True\n",
    "        return abs(height(root.left) - height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        hei = self.getHei(root)\n",
    "        return hei != -1\n",
    "\n",
    "    def getHei(self, root: TreeNode) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "\n",
    "        left_hei = self.getHei(root.left)\n",
    "        right_hei = self.getHei(root.right)\n",
    "\n",
    "        if abs(left_hei-right_hei) > 1:\n",
    "            return -1 \n",
    "        if left_hei == -1 or right_hei == -1:\n",
    "            return -1 \n",
    "        \n",
    "        return max(left_hei, right_hei) + 1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        # height_l, is_bal_l = self.get_height(root.left)\n",
    "        # height_r, is_bal_r = self.get_height(root.right)\n",
    "        # is_bal_l = self.isBalanced(root.left)\n",
    "        # is_bal_r = self.isBalanced(root.right)\n",
    "        # if abs(height_l -height_r) <= 1 and is_bal_l and is_bal_r:\n",
    "        #     return True\n",
    "        height, is_bal =  self.get_height(root)\n",
    "        return is_bal\n",
    "\n",
    "    def get_height(self, root):\n",
    "        if not root:\n",
    "            return 0, True\n",
    "        height_l, is_bal_l = self.get_height(root.left)\n",
    "        height_r, is_bal_r = self.get_height(root.right)\n",
    "        height = max(height_l, height_r) + 1\n",
    "        if abs(height_l -height_r) <= 1 and is_bal_l and is_bal_r:\n",
    "            return height, True\n",
    "        return height, False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def calc_height(self, node: TreeNode) -> int:\n",
    "        if not node.left and not node.right:\n",
    "            height = 1\n",
    "        else:\n",
    "            height_l = 0\n",
    "            height_r = 0\n",
    "            if node.left:\n",
    "                height_l = self.calc_height(node.left)\n",
    "            if node.right:\n",
    "                height_r = self.calc_height(node.right)\n",
    "            height = 1 + max(height_l, height_r)\n",
    "        return height\n",
    "    \n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        \n",
    "        left_child = 0\n",
    "        right_child = 0\n",
    "        if root.left:\n",
    "            left_child = self.calc_height(root.left)\n",
    "        if root.right:\n",
    "            right_child = self.calc_height(root.right)\n",
    "        \n",
    "        if abs(left_child-right_child)>1:\n",
    "            return False\n",
    "\n",
    "        return self.isBalanced(root.left) and self.isBalanced(root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        def treehigh(node, depth):\n",
    "            if not node:\n",
    "                return depth\n",
    "            return max(treehigh(node.left, depth + 1), treehigh(node.right, depth + 1))\n",
    "        if not root:\n",
    "            return True\n",
    "        if abs(treehigh(root.left, 0) - treehigh(root.right, 0)) <= 1:\n",
    "            return self.isBalanced(root.left) and self.isBalanced(root.right)\n",
    "        return False \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "        ans = True\n",
    "        def f(o):\n",
    "            nonlocal ans\n",
    "            if not o: return 0\n",
    "            l = f(o.left)\n",
    "            r = f(o.right)\n",
    "            if abs(l - r) > 1: ans = False\n",
    "            return max(l, r) + 1\n",
    "        f(root)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "      self.ret= False\n",
    "      def dfs(root,depth= 0):\n",
    "        if root and not self.ret:\n",
    "          left,ld = dfs(root.left,depth+1)\n",
    "          right,rd = dfs(root.right,depth+1)\n",
    "          if left and right and abs(ld-rd)<2:\n",
    "            return True,max(ld,rd)\n",
    "          else:\n",
    "            return False,max(ld,rd)\n",
    "        else:\n",
    "          return True,depth\n",
    "      return dfs(root)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isBalanced(self, root: TreeNode) -> bool:\n",
    "      self.ret= False\n",
    "      def dfs(root,depth= 0):\n",
    "        if root and not self.ret:\n",
    "          left,ld = dfs(root.left,depth+1)\n",
    "          right,rd = dfs(root.right,depth+1)\n",
    "          if left and right and abs(ld-rd)<2:\n",
    "            return True,max(ld,rd)\n",
    "          else:\n",
    "            return False,max(ld,rd)\n",
    "        else:\n",
    "          return True,depth\n",
    "      return dfs(root)[0]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
